Linked lists are linear data structures used to store and organise data in memory. It is an important concept of data structures and helps to utilise memory efficiently by dynamically allocating nodes when needed. C language linked list is a collection of nodes, where each node contains a data element and a reference (called pointer) to the next node in the sequence.
Unlike arrays, which are less flexible and take more time for insertion and deletion operations; linked list programs in C are fast and offer flexibility in size and memory utilisation. If you are interested in gaining further knowledge about this field, we suggest you check Online C Certification Courses.
The basic building block of a linked list in C is a node, and a node contains two fields: a data field to store the actual information and a reference or pointer field to link it to the next node in the sequence. The last node in the list usually points to a null value, indicating the end of the list.
It is important to understand the basic structure of a linked list node before diving deep into its implementation. The linked list in C node consists of two primary components: Data Field and Pointer (Reference).
The data field of a linked list node holds the actual information that the node is intended to store. This can be any data type, depending on the requirements of the specific linked list.
For example, if the linked list is meant to store integers, the data field would be of type int. Similarly, the data field would be of type char for a linked list of strings.
The pointer field in the node structure is important for maintaining the linkage between nodes in the linked list. This pointer, often named 'next' or 'link', points to the memory location of the next node in the sequence. It is the pointer that allows the creation of a chain of nodes where each node knows the location of the next one.
struct Node {
// Data field where value needs to be stored
int data;
// next is the pointer to the next node
struct Node* next;
};
Note: This linkage of linked lists is what gives the C program its dynamic nature, as nodes can be easily added or removed by updating these pointers.
Also read:
There are many types of linked lists that includes singly, doubly, circular, doubly circular, and header linked lists. But, here, we will discuss in detail only two popular linked lists- singly linked list and doubly linked list.
The singly linked list is the most simple form of a linked list. Each node of a linked list contains data and a pointer to the next node that forms a unidirectional sequence. The last node point of a linked list is NULL which marks the end of the list. The following example shows the singly linked list code in C:
// Syntax of a singly linked list node
struct Node {
int data;
struct Node* next;
};
A doubly linked list in C is a type of linked list where each node not only points to the next node but also points to the previous node. This bidirectional connection allows for easier traversal both forward and backward through the list. This feature is particularly useful for operations like reverse traversal or efficient insertion and deletion at both ends of the list.
// Example of a doubly linked list node
struct Node {
int data;
struct Node* next;
struct Node* prev; // Pointer to the previous node
};
Also read:
Implementing a singly linked list in C is a foundational skill for any computer programmer who aims to master dynamic data structures. A singly linked list is a versatile and memory-efficient data structure. It is important to understand its implementation, as it provides insights into fundamental programming concepts such as pointers and memory management.
Below, we have covered fundamental operations such as creating a node, inserting a node at the beginning, and traversing the singly linked list in C.
To create a new node, we need to first define a function that allocates memory for the node and initialises its data and next pointer.
Code:
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
To insert a node at the beginning of the list, first, we create a new node and update the next pointer to point to the current head of the list.
Code:
struct Node* insertAtBeginning(struct Node* head, int value) {
struct Node* newNode = createNode(value);
newNode->next = head;
return newNode;
}
Traversing a linked list means moving through each node in the list, one by one, starting from the first node (head) and continuing until the last node (NULL). Linked list in C, where nodes are connected through pointers; traversing allows programmers to explore and interact with the elements sequentially.
Unlike arrays, linked lists do not provide direct access to elements based on indices. A systematic traversal from the beginning to the end or vice versa is important to access the data elements in the linked list in C.
Traversing is fundamental for performing operations like printing all elements in the list, searching for a specific value, counting nodes, or performing any operation that requires accessing every node sequentially.
Code:
// The head is the starting point of the linked list.
void traverseList(struct Node* head) {
// Declare a pointer 'current' and initialise it with the head of the linked list.
struct Node* current = head;
while (current != NULL)
// Move the 'current' pointer to the next node in the linked list.
// This step is important for iterating through the entire list.
{
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// Print "NULL" to indicate the end of the linked list after the while loop.
If we define a structure named `Node` in this C program and add a `main()` function with some values, the output will be:
Related: Popular Programming Courses From Top Providers
A linked list offers a dynamic and efficient way to manage data. Whether it is a singly linked list for one-directional traversal or a doubly linked list for bidirectional traversal, the principle remains the same as the above-provided C linked list example.
A linked list in C is a data structure consisting of nodes, where each node contains data and a reference (or link) to the next node in the sequence. This structure allows for dynamic memory allocation and efficient data manipulation.
The two primary types are Singly Linked List in which each node contains data and a pointer to the next node in the sequence and Doubly Linked List in which Nodes have data, a pointer to the next node, and a pointer to the previous node, enabling bidirectional traversal.
To create a node in a linked list, you allocate memory for the node, set its data, and initialise the next (and prev for doubly linked lists) pointer. This creates a new element ready to be added to the linked list.
To traverse a linked list in C, iterate through each node, and perform actions like printing data. This involves moving from one node to the next (or previous for doubly linked lists) until reaching the end of the list.
Inserting a node at the beginning involves creating a new node, setting its next (and prev for doubly linked lists) pointer to the current head, and updating the head to the new node.
Application Date:05 September,2024 - 25 November,2024
Application Date:15 October,2024 - 15 January,2025
Application Date:10 November,2024 - 08 April,2025